#include <iostream>
#include <stack>
#include <vector>

#include "common/utils.hpp"

void traversal(TreeNode* node, std::vector<int>& vec) {
    if (node == nullptr) return;

    vec.push_back(node->val);
    traversal(node->left, vec);
    traversal(node->right, vec);
}

// 前序遍历二叉树（递归）
std::vector<int> preorderTraversal(TreeNode* root) {
    std::vector<int> res;
    traversal(root, res);

    return res;
}

// 迭代
std::vector<int> preorderTraversal2(TreeNode* root) {
    std::vector<int> res;
    std::stack<TreeNode*> tnStack;
    tnStack.push(root);
    while (!tnStack.empty()) {
        TreeNode* node = tnStack.top();
        tnStack.pop();

        if (node == nullptr) {
            continue;
        }

        res.push_back(node->val);
        tnStack.push(node->right);
        tnStack.push(node->left);
    }

    return res;
}

// 方法三：统一迭代
std::vector<int> preorderTraversal3(TreeNode* root) {
    std::vector<int> result;
    std::stack<TreeNode*> st;

    if (root != nullptr) st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        if (node != NULL) {
            st.pop();

            if (node->right) st.push(node->right);

            if (node->left) st.push(node->left);

            st.push(node);
            st.push(NULL);
        } else {
            st.pop();
            result.push_back(st.top()->val);
            st.pop();
        }
    }

    return result;
}

extern TreeNode* commonRoot;
extern int commonInt;

int main() {
    std::vector<int> res = preorderTraversal3(commonRoot);
    std::cout << "preorder: \n";
    printVector(res);

    std::cout << commonInt << std::endl;
}